/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

#include <iostream>
#include <vector>
#include <queue>


using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();
		if(len == 0){
			return nullptr;
		}
		if(len == 1){
			return lists[0];
		}
		ListNode * index = lists[0];
		
		for(int i = 1; i < len; i++){
			index = mergeTwoLists(index,lists[i]);
		}
		return index;
    }
	

	// 合并两个链表的
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		ListNode * head = new ListNode(0);
		ListNode * index = head;
		
		while(list1 && list2){
			if(list1->val <= list2->val){
				index->next = list1;
				list1 = list1->next;
			}else{
				index->next = list2;
				list2 = list2->next;
			}
			index = index->next;
		}
		
		if(list1){
			index->next = list1;
		}
		if(list2){
			index->next = list2;
		}
		head = head->next;
		return head;
    }
	
	ListNode * init(vector<int> nums){
		int len = nums.size();
		if(len == 0){
			return nullptr;
		}
		
		ListNode * head = new ListNode;
		head->val = nums[0];
		head->next = nullptr;
		if(len == 1){
			return head;
		}
		ListNode * index = head;
		for(int i = 1; i < len; i++){
			ListNode * tmp = new ListNode;
			tmp->val = nums[i];
			tmp->next = nullptr;
			index->next = tmp;
			index = tmp;
		}
		return head;
	}

	void show(ListNode * head){
		while(head){
			cout << head->val << ",";
			head = head->next;
		}
		cout << endl;
	}
	
	// 优先队列 对头元素最大
	struct Comp{
		bool operator()(ListNode * l1, ListNode * l2){
			return l1->val >= l2->val;
		}
	};
	
	ListNode * mergeKLists1(vector<ListNode*>& lists){
		priority_queue<ListNode*, vector<ListNode*>, Comp> pq;
		int len = lists.size();
		for(int i = 0; i < len; i++){
			if(lists[i]){
				pq.push(lists[i]);
			}
		}
		ListNode * newHead = new ListNode();
		ListNode * node = newHead;
		while(!pq.empty()){
			ListNode * tmp = pq.top();
			pq.pop();
			if(tmp->next){
				pq.push(tmp->next);
			}
			node->next = tmp;
			node = node->next;
		}
		return newHead->next;
	}
};

int main(){
	Solution so;
	vector<ListNode *> lists;
	ListNode * n1 = so.init({1,2,3});
	ListNode * n2 = so.init({-1,1,3,4});
	ListNode * n3 = so.init({3,4,5,6,8});
	lists.push_back(n1);
	lists.push_back(n2);
	lists.push_back(n3);
	ListNode * node = so.mergeKLists(lists);
	so.show(node);
	return 0;
}